package com.gs.coursera.algorithms.core.graph;

import java.util.BitSet;

import com.gs.coursera.algorithms.core.collection.MinPQ;
import com.gs.coursera.algorithms.core.collection.Queue;
import com.gs.coursera.algorithms.core.uf.QuickUnion;
import com.gs.coursera.algorithms.core.uf.UnionFind;

public class HammingKruskalMst extends MinimumSpaningTree<BitSet, Integer>{

	private Queue<Edge<BitSet, Integer>> mst;
	public HammingKruskalMst(Graph<BitSet, Integer> graph) {
		super(graph);
		mst = new Queue<Edge<BitSet,Integer>>();
		findMst();
	}

	@Override
	public Queue<Edge<BitSet, Integer>> findMst() {
		mst = new Queue<Edge<BitSet,Integer>>();
		MinPQ<Edge<BitSet, Integer>> pq = new MinPQ<Edge<BitSet,Integer>>(graph.getEdges());
		UnionFind uf = new QuickUnion(graph.getVertexCount());
		while(!pq.isEmpty() && mst.size() < graph.getVertexCount()-1){
			Edge<BitSet, Integer> e = pq.delMin();
			Vertex<BitSet, Integer> v = e.getStartVertex();
			Vertex<BitSet, Integer> w = e.getEndVertex();
			if(uf.isConnected(v.getVertexNumber(), w.getVertexNumber())){
				continue;
			}
			uf.union(v.getVertexNumber(), w.getVertexNumber());
			mst.enqueue(e);
		}
		return mst;
	}
	
	public Integer maxClusterSpace(int k){
		Queue<Edge<BitSet,Integer>> mst = new Queue<Edge<BitSet,Integer>>();
		MinPQ<Edge<BitSet, Integer>> pq = new MinPQ<Edge<BitSet,Integer>>(graph.getEdges());
		UnionFind uf = new QuickUnion(graph.getVertexCount());
		boolean[] connectedVertex = new boolean[graph.getVertexCount()];
		for (int i = 0; i < connectedVertex.length; i++) {
			connectedVertex[i] = false;
		}
		int count = 0;
		int clusterCount = graph.getVertexCount();
		Integer maxSpace = 0;
		while(!pq.isEmpty() ){
			count =0;
			for (int i = 0; i < connectedVertex.length; i++) {
				if(connectedVertex[i])
					count ++;
			}
			clusterCount = graph.getVertexCount() - count + 1;
			if(clusterCount == k)
				break;
			Edge<BitSet, Integer> e = pq.delMin();
			Vertex<BitSet, Integer> v = e.getStartVertex();
			Vertex<BitSet, Integer> w = e.getEndVertex();
			if(uf.isConnected(v.getVertexNumber(), w.getVertexNumber())){
				continue;
			}
			uf.union(v.getVertexNumber(), w.getVertexNumber());
			connectedVertex[e.getStartVertex().getVertexNumber()] = true;
			connectedVertex[e.getEndVertex().getVertexNumber()] = true;
			maxSpace = e.getWeight();
		}
		
		return maxSpace;
	}

	@Override
	public Integer getTotalWeight() {
		Integer weight = 0;
        for (Edge<BitSet, Integer> e : mst)
            weight += e.getWeight();
        return weight;
	}
}
